/*
 * SimpleCD List Management - Arduino Library Extension
 * 链表管理模块 - Arduino库扩展
 * 
 * 模块描述：
 * 为CDBUS协议栈提供高效的链表数据结构和操作接口
 * 支持嵌入式环境下的内存高效管理
 * 
 * 设计特点：
 * - 轻量级设计，适用于资源受限的嵌入式系统
 * - 支持C/C++混合编程
 * - 提供类型安全的链表操作宏
 * - 零拷贝设计，减少内存碎片
 * 
 * 版权信息：
 * Copyright (c) 2024
 * Licensed under MIT License
 * 
 * 原作者：Duke Fong <d@d-l.io>
 * 修改：mastwet@Undefine Innovation
 */

/**
 * @file cd_list.h
 * @brief 链表管理模块 - Arduino库扩展
 * @details 为CDBUS协议栈提供高效的链表数据结构和操作接口
 *          支持嵌入式环境下的内存高效管理
 * 
 * @author 原作者：Duke Fong <d@d-l.io>
 * @author 修改团队：mastwet@Undefine Innovation
 * @date 2024
 * @copyright MIT License
 * 
 * @note 轻量级设计，适用于资源受限的嵌入式系统
 * @note 提供类型安全的链表操作宏，支持C/C++混合编程
 */

#ifndef CD_LIST_H
#define CD_LIST_H

#include <Arduino.h>

#ifdef __cplusplus
extern "C" {
#endif

/**
 * @defgroup list_structures 链表数据结构
 * @brief 链表核心数据结构定义
 * @{
 */

/**
 * @brief 链表节点结构体
 * @details 作为链表的基本组成单元，包含指向下一节点的指针
 * @note 用户数据结构应包含此结构体作为成员变量
 * 
 * 使用示例：
 * @code
 * typedef struct {
 *     list_node_t node;    // 必须作为第一个成员
 *     uint8_t data[64];    // 用户数据
 *     uint16_t len;        // 数据长度
 * } my_packet_t;
 * @endcode
 */
typedef struct list_node {
   struct list_node *next;  /**< 指向下一个节点的指针 */
} list_node_t;

/**
 * @brief 链表头结构体
 * @details 管理整个链表，包含头尾指针和长度信息
 * @note 使用前必须通过list_head_init进行初始化
 */
typedef struct {
    list_node_t *first;  /**< 指向链表首节点 */
    list_node_t *last;   /**< 指向链表尾节点 */
    uint32_t    len;     /**< 链表中当前节点数量 */
} list_head_t;

/** @} */ // 链表数据结构组结束

/**
 * @defgroup list_operations 链表操作函数
 * @brief 链表基本操作接口
 * @{
 */

/**
 * @brief 从链表头部获取并移除一个节点
 * @param head 链表头指针
 * @return 成功返回链表首节点指针，失败返回NULL
 * @note 该操作会从链表中移除节点，调用者负责释放内存
 * @note 时间复杂度：O(1)
 */
list_node_t *list_get(list_head_t *head);

/**
 * @brief 在链表尾部插入一个节点
 * @param head 链表头指针
 * @param node 要插入的节点指针
 * @note 该节点会被添加到链表末尾，时间复杂度：O(1)
 * @note 节点必须是有效的已分配内存，且next指针应为NULL
 */
void list_put(list_head_t *head, list_node_t *node);

/**
 * @brief 从链表尾部获取并移除一个节点
 * @param head 链表头指针
 * @return 成功返回链表尾节点指针，失败返回NULL
 * @note 该操作会从链表中移除节点，调用者负责释放内存
 * @note 时间复杂度：O(n)，需要遍历链表找到倒数第二个节点
 */
list_node_t *list_get_last(list_head_t *head);

/**
 * @brief 在链表头部插入一个节点
 * @param head 链表头指针
 * @param node 要插入的节点指针
 * @note 该节点会被添加到链表头部，时间复杂度：O(1)
 * @note 节点必须是有效的已分配内存
 */
void list_put_begin(list_head_t *head, list_node_t *node);

/**
 * @brief 从链表中移除指定节点
 * @param head 链表头指针
 * @param pre 要移除节点的前驱节点指针（如为NULL表示移除首节点）
 * @param node 要移除的节点指针
 * @note 该操作会从链表中移除节点但不释放内存，调用者负责释放
 * @note 时间复杂度：O(1)（已知前驱节点的情况下）
 */
void list_pick(list_head_t *head, list_node_t *pre, list_node_t *node);

/**
 * @brief 将指定节点移动到链表头部
 * @param head 链表头指针
 * @param pre 要移动节点的前驱节点指针（如为NULL表示移动首节点）
 * @param node 要移动的节点指针
 * @note 该操作会先移除节点再插入到头部，时间复杂度：O(1)
 * @note 节点必须存在于链表中，否则行为未定义
 */
void list_move_begin(list_head_t *head, list_node_t *pre, list_node_t *node);

/** @} */ // 链表操作函数组结束

/**
 * @defgroup list_macros 链表操作宏定义
 * @brief 类型安全的链表操作宏
 * @{
 */

/**
 * @brief 根据成员指针获取包含结构体指针
 * @param ptr 成员变量指针
 * @param type 包含结构体类型
 * @param member 成员变量名
 * @return 包含结构体指针
 * 
 * @warning ptr必须指向type结构体中的member成员
 * @note 这是Linux内核经典宏，用于从链表节点获取用户数据结构
 */
#define container_of(ptr, type, member) \
    ((type *)((uint8_t *)(ptr) - (uint8_t *)(&((type *)0)->member)))

/**
 * @brief 根据链表节点获取用户数据结构
 * @param ptr 链表节点指针
 * @param type 用户数据结构类型
 * @return 用户数据结构指针
 * 
 * @note 要求用户数据结构中链表节点名为'node'
 */
#define list_entry(ptr, type) \
    container_of(ptr, type, node)

/**
 * @brief 安全版本的list_entry，支持NULL检查
 * @param ptr 链表节点指针（可为NULL）
 * @param type 用户数据结构类型
 * @return 有效时返回用户数据结构指针，NULL时返回NULL
 */
#define list_entry_safe(ptr, type) ({ \
        list_node_t *__ptr = (ptr); \
        __ptr ? container_of(__ptr, type, node) : NULL; \
    })

/**
 * @brief 从链表头部获取节点并转换为用户数据结构
 * @param head 链表头指针
 * @param type 用户数据结构类型
 * @return 成功返回用户数据结构指针，失败返回NULL
 * 
 * @note 等同于list_entry_safe(list_get(head), type)
 */
#define list_get_entry(head, type) \
        list_entry_safe(list_get(head), type)

/**
 * @brief 链表遍历宏（可修改链表）
 * @param head 链表头指针
 * @param pre 前驱节点指针变量
 * @param pos 当前节点指针变量
 * 
 * @note 支持在遍历过程中删除当前节点
 * @warning 不要在循环体中修改pre和pos变量
 */
#define list_for_each(head, pre, pos) \
    for (pre = NULL, pos = (head)->first; pos != NULL; \
         pre = pos, pos = (pos ? (pos)->next : (head)->first))

/**
 * @brief 链表只读遍历宏
 * @param head 链表头指针
 * @param pos 当前节点指针变量
 * 
 * @note 仅用于遍历，不支持修改链表结构
 * @warning 循环体中不要修改链表结构
 */
#define list_for_each_ro(head, pos) \
    for (pos = (head)->first; pos != NULL; \
         pos = (pos ? (pos)->next : (head)->first))

/**
 * @brief 初始化链表头结构
 * @param head 链表头指针
 * 
 * @note 将链表头所有字段清零，必须在首次使用前调用
 */
#define list_head_init(head) \
    memset(head, 0, sizeof(list_head_t))

/** @} */ // 链表操作宏定义组结束

#ifdef __cplusplus
}
#endif

#endif // CD_LIST_H